package baseclass.a_sort.mergeSort;

/**
 * 在一个数组中， 左边的数如果比右边的数大， 则这两个数构成一个逆序对，
 * 请打印所有逆序对
 * <p>
 * 分析：同小数问题，只不过是 求和换成打印，并且是左边大于右边
 * 所以要从大到小排序。
 * 如果左块有一个 i大于 右块j ，则由于从小到大，则i位置大于所有 j到R位置的元素
 * <p>
 * <p>
 * 可以通过打印信息来理解程序执行的流程
 *
 * @date 2020/2/26 19:56
 **/
public class 逆序对 {
    public static void main(String[] args) {
//        int [] arr ={1,3,4,2};
//        int [] arr ={1,7,4,2};
        int[] arr = {1, 7, 9, 5, 2, 6, 8, 0};
        solution(arr);
        System.out.println();
        mergeSort(arr);
//        System.out.println(Arrays.toString(arr));
    }

    public static void solution(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    System.out.print("(" + arr[i] + "," + arr[j] + "),");
                }
            }
        }
    }

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        sortProcess(arr, 0, arr.length - 1);
    }

    private static void sortProcess(int[] arr, int l, int r) {

        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        // T(N/2)  规模
        sortProcess(arr, l, mid);
        // T(N/2)  规模
        sortProcess(arr, mid + 1, r);
        // o(N)    其他操作复杂度
        merge(arr, l, mid, r);
        // T(N) = 2T(N/2) + o(N)
    }


    private static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int p1 = l;
        int p2 = mid + 1;
        int i = 0;

        //方式1：从大到小排序，左侧数组如果p1大于p2位置元素，那么p1比 p2-r的都大
        while (p1 <= mid && p2 <= r) {
            //  在merge成有序数组之前找出所有逆序对
            if (arr[p1] > arr[p2]) {
                //System.out.println("merge invoke!");
                for (int j = p2; j <= r; j++) {
                    System.out.print("(" + arr[p1] + "," + arr[j] + "),");
                }
            }
            //  谁大把谁放入辅助数组，然后自增
            help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
        }
        //方式2：从小到大排序。左侧数组如果p1大于p2位置的元素，那么p1比 mid+1 -p2都大
        /*方式2会产生BUG，原因：如left = {1,7} right={2,4}
        p2 = 0,那么7比2大，输出(7,2)，
        p2 = 1,那么7比4大，输出(7,2),(7,4)显然多算了一次(7,2)。
        重复的原因是，p2移动过程中，有可能一直比p1小，那么mid - p2之间的数可能会被重复计算多次。
        如果是从大到小排序{7，1｝  ｛4，2｝
            P1=7,比4大。所以输出(7,4),(7,2)。然后较大的数7被排除，走向1.所以不会导致重复。*/
        /*while (p1 <= mid && p2 <= r) {
            if (arr[p1] > arr[p2]) {
                for (int j = mid + 1; j <= p2; j++) {
                    System.out.print("(" + arr[p1] + "," + arr[j] + "),");
                }
            }
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        正确的从小到大方式： p1处比p2 大，那么p1-mid都比p2大，并且p2会++，
        所以不会再产生和p2重复的了。已经测试过！
            while (p1 <= mid && p2 <= r) {
            if (arr[p1] > arr[p2]) {
                for (int j = p1; j <= mid ; j++) {
                    System.out.print("(" + arr[p1] + "," + arr[j] + "),");
                }
            }
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        */
        // 必有且只有一个数组排完，下面只会发生一个
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }

        while (p2 <= r) {
            help[i++] = arr[p2++];
        }

        //拷贝到原数组
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }
}
